User blog:LittlePeng9/Advent calendar
So, it's December, and in few weeks Christmas is coming! Because of this I have decided to make something of sort of advent calendar. I won't be giving out chocolates, but I'll be describing some mathematical facts which I, for some or other reason, have found especially interesting. I wish you have fun pre-Christmas! #Pizza theorem - take any point inside a disk, and draw 4 straight lines through it, with equal angles between them. This way we will get disk divided into 8 pieces. Number them 1,...,8 in clockwise order. Then sum of areas of pieces 1,3,5,7 is equal to sum of areas of pieces 2,4,6,8. #Laczkovich's solution to Tarski's circle-squaring problem - it is possible to divide a disk into finitely many pieces and rearrange them into square of the same area. Original dissection requires only 1050 pieces! #Completeness of Presburger arithmetic - axioms of Presburger arithmetic are able to prove, for every statement in corresponding language, the statement or its negation. Moreover, this implies that there exists a procedure which decides which of these holds. That means we can effectively verify truth of any statement involving addition only. #Fermat's last theorem for polynomials - suppose P, Q, R are pairwise relatively prime polynomials (with integer/rational/real/complex coefficients) satisfying Pn+Qn=Rn for some n>2. Then all of P, Q, R are all constant. #Immerman-Szelepcsenyi theorem - if decision problem P(n) can be solved in nondeterministic space f(n) (for f at least logarithmic) then so can be complement problem ~P(n). #Riemann's rearrangement theorem - let the series \(\sum_{n=1}^\infty a_n\), for \(a_n\in\Bbb R\), converge conditionally (i.e. not absolutely). Then, for any real number \(M\) we can find some permutation \(b_n\) of \(a_n\) such that \(\sum_{n=1}^\infty b_n=M\). In other words, we can rearrange terms of conditionally convergent series to reach any real value. #Pólya's recurrence theorem - random walk on \(\Bbb Z^2\) lattice will visit every point of the lattice infinitely many times with probability 1. #Kunen's inconsistency theorem - let \(j\) be an elementary embedding of \(V\) to itself (i.e. it's a class function which preserves truth of formulas). Then \(j\) is trivial, that is, \(j(a)=a\) for all \(a\). #Nondiamond theorem - suppose we have two recursively enumerable sets such the only sets which they both can decide are decidable, and every set which can decide both of these sets can also solve halting problem. Then one of these sets is computable, and the other one can solve halting problem. #Ford's zero-free regions for \(\zeta(s)\) - if \(\zeta(\sigma+it)=0\) for \(0\leq\sigma\leq 1\), then \(\sigma\leq 1-\frac{1}{57.54(\log|t|)^\frac{2}{3}(\log\log|t|)^\frac{1}{3}}\). This is closest we are to Riemann hypothesis, which states \(\sigma\leq\frac{1}{2}\). #Heterogeneous tiling of the plane - it is possible to tile the whole plane using squares of every integer size exactly once. #Strong form of Dirichlet's theorem - sum of reciprocal of primes in any integer arithmetic progression diverges. #Strength of random oracles - suppose that the probability that a fixed set \(A\) is computable relatively to a random set \(B\) is greater than 0. Then \(A\) is computable. #Sophomore's dream - \(\int_0^1 x^{-x}\mathrm{d}x=\sum_{n=1}^\infty n^{-n}\) #Freshman's dream - let \(p\) be a prime number. Then \((x+y)^p=x^p+y^p\). #Picard's little theorem - if \(f\) is an entire complex function, and there exist two complex numbers which aren't taken by \(f\) as values, then \(f\) is constant. #Legendre's three-square theorem - non-negative integer can be expressed as \(x^2+y^2+z^2\) for \((x,y,z)\in\Bbb Z^3\) iff it's not of the form \(4^k(8l+7)\). #Hindman's theorem - let's call a subset of \(\Bbb N\) an IP set if it contains all finite sums of elements of some its infinite subset. Every finite partition of an IP set contains an IP set. #\(\text{MIP}=\text{NEXPTIME}\) - problems which can be solved by an interactive proof system between one verifier and two independent provers in polynomial time are precisely the problems solvable nondeterministically in exponential time. #Hilbert's inequality - let \(x_i\) be a sequence of complex numbers. Then \(|\sum_{n\neq m}\frac{x_n\overline{x_m}}{n-m}|\leq\pi\sum_n |x_n|^2\), provided RHS converges. Moreover, constant \(\pi\) cannot be improved. #Heath-Brown's result on Artin's conjecture - for every non-square integer \(n\neq-1\) there exist infinitely many primes \(p\) such that \(n\) is primitive root modulo \(p\), with at most three exceptions, out of which at most two are prime. No value of \(n\) is known for which it holds. #Maier's theorem - denote \(\Delta(x,\delta)=\pi(x+\delta)-\pi(x)\). Then it's not true that \(\Delta(x,(\log x)^\lambda)\sim \frac{(\log x)^\lambda}{\log x}\) for any \(\lambda>1\). That is, prime number theorem doesn't hold in short (polylogarithmically sized) intervals. #\(\text{P}\) vs \(\text{NP}\) relative to random oracles - given random oracle \(A\), \(\text{P}^A\neq\text{NP}^A\) with probability 1. #Christmas stocking theorem - \(\sum_{i=0}^{k-1}{n+i \choose i}={k+n\choose k-1}\) Merry Christmas and Happy Holidays, everyone! Category:Blog posts